#include "heap.h"
void Swap(int* x,int* y)//交换
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
void AdjustDown(int *arr,int parent,int size)//向下调整，组成大堆
{
    int child = parent*2 + 1;
    while (child < size)
    {
        if(child + 1 < size && arr[child] < arr[child+1])
        {
            child = child + 1;
        }
        if(arr[parent] < arr[child])
        {
            Swap(&arr[parent],&arr[child]);
            parent = child;
            child = parent*2 + 1;
        }
        else
        {
            break;
        }

    }
}
void HeapSort(int* arr,int len) //堆排序
{
    for(int i = (len-1-1)/2; i >= 0; i--)
    {
        AdjustDown(arr,i,len);
    }
    int end = len;
    while(end--)
    {
        Swap(&arr[0],&arr[end]);
        AdjustDown(arr,0,end);
    }
}